﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int QDataType;
typedef struct QueueNode {
    QDataType data;
    struct QueueNode* next;
} QueueNode;

typedef struct Queue {
    QueueNode* phead;
    QueueNode* ptail;
    int size; // 保存队列有效数据个数
} Queue;

void QueueInit(Queue* pq) {
    assert(pq);
    pq->phead = pq->ptail = NULL;
    pq->size = 0;
}
// ⼊队列，队尾
void QueuePush(Queue* pq, QDataType x) {
    assert(pq);
    // 申请新节点
    QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
    if (newnode == NULL) {
        perror("malloc fail!");
        exit(1);
    }
    newnode->data = x;
    newnode->next = NULL;

    // ptail newnode
    if (pq->phead == NULL) { // 队列为空
        pq->phead = pq->ptail = newnode;
    }
    else {
        // 队列不为空
        pq->ptail->next = newnode;
        pq->ptail = pq->ptail->next; // newnode
    }
    pq->size++;
}

// 队列判空
bool QueueEmpty(Queue* pq) {
    assert(pq);
    return pq->phead == NULL && pq->ptail == NULL;
}

// 出队列，队头
void QueuePop(Queue* pq) {
    assert(pq);
    assert(!QueueEmpty(pq));

    // 只有一个结点的情况，避免ptail变成野指针
    if (pq->ptail == pq->phead) {
        free(pq->phead);
        pq->phead = pq->ptail = NULL;
    }
    else {
        // 删除队头元素、
        QueueNode* next = pq->phead->next;
        free(pq->phead);
        pq->phead = next;
    }
    --pq->size;
}
// 取队头数据
QDataType QueueFront(Queue* pq) {
    assert(pq);
    assert(!QueueEmpty(pq));

    return pq->phead->data;
}

// 取队尾数据
QDataType QueueBack(Queue* pq) {
    assert(pq);
    assert(!QueueEmpty(pq));

    return pq->ptail->data;
}
// 队列有效元素个数
int QueueSize(Queue* pq) {
    assert(pq);
    /*int size = 0;
    QueueNode* pcur = pq->phead;
    while (pcur)
    {
        size++ ;
        pcur = pcur->next;
    }
    return size;*/
    return pq->size;
}

// 销毁队列
void QueueDestroy(Queue* pq) {
    assert(pq);
    // assert(!QueueEmpty(pq));

    QueueNode* pcur = pq->phead;
    while (pcur) {
        QueueNode* next = pcur->next;
        free(pcur);
        pcur = next;
    }
    pq->phead = pq->ptail = NULL;
    pq->size = 0;
}

typedef struct {
    Queue q1;
    Queue q2;
} MyStack;

MyStack* myStackCreate() {
    MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
    QueueInit(&pst->q1);
    QueueInit(&pst->q2);
    return pst;
}

void myStackPush(MyStack* obj, int x) {
    // 往不为空的队列中插入数据
    if (!QueueEmpty(&obj->q1))
        QueuePush(&obj->q1, x);
    else {
        QueuePush(&obj->q2, x);
    }
}

int myStackPop(MyStack* obj) {
    Queue* empQ = &obj->q1;
    Queue* noneQ = &obj->q2;
    if (!QueueEmpty(&obj->q1)) {
        noneQ = &obj->q1;
        empQ = &obj->q2;
    }
    // 将不为空队列中size-1个数据导入到空队列中
    while (QueueSize(noneQ) > 1) {
        int front = QueueFront(noneQ);
        QueuePush(empQ, front);
        QueuePop(noneQ);
    }
    // 非空队列中只剩下一个数据---要出栈的数据
    int pop = QueueFront(noneQ);
    QueuePop(noneQ);
    return pop;
}

// 取栈顶元素----取非空队列中的队尾元素
int myStackTop(MyStack* obj) {
    if (!QueueEmpty(&obj->q1)) {
        return QueueBack(&obj->q1);
    }
    else {
        return QueueBack(&obj->q2);
    }
}

bool myStackEmpty(MyStack* obj) {
    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

void myStackFree(MyStack* obj) {
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
    obj = NULL;
}


typedef int QDataType;
typedef struct QueueNode {
    QDataType data;
    struct QueueNode* next;
} QueueNode;

typedef struct Queue {
    QueueNode* phead;
    QueueNode* ptail;
    int size; // 保存队列有效数据个数
} Queue;

void QueueInit(Queue* pq) {
    assert(pq);
    pq->phead = pq->ptail = NULL;
    pq->size = 0;
}
// ⼊队列，队尾
void QueuePush(Queue* pq, QDataType x) {
    assert(pq);
    // 申请新节点
    QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
    if (newnode == NULL) {
        perror("malloc fail!");
        exit(1);
    }
    newnode->data = x;
    newnode->next = NULL;

    // ptail newnode
    if (pq->phead == NULL) { // 队列为空
        pq->phead = pq->ptail = newnode;
    }
    else {
        // 队列不为空
        pq->ptail->next = newnode;
        pq->ptail = pq->ptail->next; // newnode
    }
    pq->size++;
}

// 队列判空
bool QueueEmpty(Queue* pq) {
    assert(pq);
    return pq->phead == NULL && pq->ptail == NULL;
}

// 出队列，队头
void QueuePop(Queue* pq) {
    assert(pq);
    assert(!QueueEmpty(pq));

    // 只有一个结点的情况，避免ptail变成野指针
    if (pq->ptail == pq->phead) {
        free(pq->phead);
        pq->phead = pq->ptail = NULL;
    }
    else {
        // 删除队头元素、
        QueueNode* next = pq->phead->next;
        free(pq->phead);
        pq->phead = next;
    }
    --pq->size;
}
// 取队头数据
QDataType QueueFront(Queue* pq) {
    assert(pq);
    assert(!QueueEmpty(pq));

    return pq->phead->data;
}

// 取队尾数据
QDataType QueueBack(Queue* pq) {
    assert(pq);
    assert(!QueueEmpty(pq));

    return pq->ptail->data;
}
// 队列有效元素个数
int QueueSize(Queue* pq) {
    assert(pq);
    /*int size = 0;
    QueueNode* pcur = pq->phead;
    while (pcur)
    {
        size++ ;
        pcur = pcur->next;
    }
    return size;*/
    return pq->size;
}

// 销毁队列
void QueueDestroy(Queue* pq) {
    assert(pq);
    // assert(!QueueEmpty(pq));

    QueueNode* pcur = pq->phead;
    while (pcur) {
        QueueNode* next = pcur->next;
        free(pcur);
        pcur = next;
    }
    pq->phead = pq->ptail = NULL;
    pq->size = 0;
}

typedef struct {
    Queue q1;
    Queue q2;
} MyStack;

MyStack* myStackCreate() {
    MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
    QueueInit(&pst->q1);
    QueueInit(&pst->q2);
    return pst;
}

//入栈
void myStackPush(MyStack* obj, int x) {
    // 往不为空的队列中插入数据
    if (!QueueEmpty(&obj->q1))
        QueuePush(&obj->q1, x);
    else {
        QueuePush(&obj->q2, x);
    }
}

//出栈
int myStackPop(MyStack* obj) {
    Queue* empQ = &obj->q1;      //为空
    Queue* noneQ = &obj->q2;     //不为空
    if (!QueueEmpty(&obj->q1)) {
        noneQ = &obj->q1;
        empQ = &obj->q2;
    }
    // 将不为空队列中size-1个数据导入到空队列中
    while (QueueSize(noneQ) > 1) {
        int front = QueueFront(noneQ);
        QueuePush(empQ, front);
        QueuePop(noneQ);
    }
    // 非空队列中只剩下一个数据---要出栈的数据
    int pop = QueueFront(noneQ);
    QueuePop(noneQ);
    return pop;
}

// 取栈顶元素----取非空队列中的队尾元素
int myStackTop(MyStack* obj) {
    if (!QueueEmpty(&obj->q1)) {
        return QueueBack(&obj->q1);
    }
    else {
        return QueueBack(&obj->q2);
    }
}

bool myStackEmpty(MyStack* obj) {
    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

void myStackFree(MyStack* obj) {
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
    obj = NULL;
}

/**
 * Your MyStack struct will be instantiated and called as such:
 * MyStack* obj = myStackCreate();
 * myStackPush(obj, x);

 * int param_2 = myStackPop(obj);

 * int param_3 = myStackTop(obj);

 * bool param_4 = myStackEmpty(obj);

 * myStackFree(obj);
*/